﻿#define _CRT_SECURE_NO_WARNINGS 1

//题目描述:
//输入两个升序序列的序列，将两个序列合并为一个有序序列并输出。
//输入包含三行，第一行包含两个正整数n, m，用空格分隔。n表示第二行第一个升序序列中数字的个
//数，m表示第三行第二个升序序列中数字的个数。其中 1 <= n <= 30, 1 <= m <= 30
//第二行包含n个整数，用空格分隔。
//第三行包含m个整数，用空格分隔。
//输出为一行，输出⻓度为n + m的升序序列
//即⻓度为n的升序序列和⻓度为m的升序序列中的元素重新进行升序序列排列合并。

//测试：
//输入：
//5 6
//1 3 7 9 22
//2 8 10 17 33 44
//输出：
//1 2 3 7 8 9 10 17 22 33 44

#include<stdio.h>

void Concat_arr(int *arr1, int *arr2,int *Arr, int n, int m)
{
	int sum = n + m;
	int i = 0;
	int j = 0;
	int k = 0;
	
	//对双方共有部分进行合并
	while (i < n && j < m)
	{
		if (arr1[i] < arr2[j])
		{
			Arr[k] = arr1[i];
			i++;
			k++;
		}
		else 
		{
			Arr[k] = arr2[j];
			j++;
			k++;
		}	
	}

	//其中一方结束后，判断其余是否有剩余数字
	if (i == n)
	{
		while (j < m && k < sum)
		{
			Arr[k] = arr2[j];
			j++;
			k++;
		}
	}

	if (j == m)
	{
		while (i < n && k < sum)
		{
			Arr[k] = arr1[i];
			i++;
			k++;
		}
	}
}

int main()
{
	int n = 0;
	int m = 0;
	scanf("%d %d", &n, &m);

	int N[30] = { 0 };
	int M[30] = { 0 };
	int Arr[60] = { 0 };

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &N[i]);
	}

	for (int i = 0; i < m; i++)
	{
		scanf("%d", &M[i]);
	}

	Concat_arr(N,M,Arr,n,m);

	for (int i = 0; i < n + m; i++)
	{
		printf("%d ", Arr[i]);
	}

	return 0;
}

//个人思路：在main函数中完成输入的操作
//进入函数完成合并数组的操作
//定义一个⻓度为n + m的新数组 arr3 ，将两个有序数组合并到 arr3 数组中，使得 arr3 数组有序。
//1. 定义一个⻓度为n + m的新数组 arr3 ，以及两个指针 i 和 j ，分别指向 arr1 和 arr2 的开头；
//2. 定义⼀个计数器 k ，初始化为 0;
//3. 比较 arr1[i] 和 arr2[j] ，将较小的数存入 arr3 中，并将对应指针向后移动一位；
//4. 将计数器 k 加 1;
//5. 重复步骤 3 和 4 直到某个指针越界;
//6. 将另⼀个指针指向的数组的剩余所有元素依次存入 arr3 中，存入同时将计数器 k 的值自增1;
//7. 至此， arr3 数组中的元素为 arr1 数组和 arr2 数组合并并排序后的结果，按序输出前k个元素即可